package leetcode;

public class NumMatrix {

    int[][] preSum;
    public NumMatrix(int[][] matrix) {

        preSum = new int[matrix.length + 1][matrix[0].length + 1];
        for (int i = 1; i <= matrix.length; i++) { // preSum[i][j] 记录matrix[0][o] ~ matrix[i-1][j-1]的矩形范围内的值的和
            for (int j = 1; j < matrix[i].length; j++) {
                preSum[i][j] = preSum[i-1][j] + preSum[i][j-1] - preSum[i-1][j-1] + matrix[i-1][j-1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return preSum[row2 + 1][col2 + 1] - preSum[row1 + 1][col2 + 1] - preSum[row2 + 1][col1 + 1]  + preSum[row1 + 1][col1 + 1];
    }
}
